#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <strings.h>

#include "common.h"
#include "cache.h"

cache_error
create_cache(CACHE *c) {
	size_t bytes;
	size_t indices;
	size_t assoc;

	bytes	= (1 << (1+c->geom.line));
	indices	= (1 << (6+c->geom.idx));
	assoc	= (1 + c->geom.assoc);

	// cache must hold a multiple of the largest possible
	// data size
	if(bytes < sizeof(sim_size) || (bytes & (sizeof(sim_size)-1)))
		return E_INVALID;

	// pre compute useful values
	c->byte_mask	= bytes-1;
	c->index_shift	= c->geom.line+1;
	c->index_mask	= (indices-1) << c->index_shift;
	c->tag_mask		= ((cache_addr)-1) ^ (c->index_mask | c->byte_mask);
	c->ways			= assoc;
	c->way_shift	= c->index_shift+(c->geom.idx+6);
	c->tag_shift	= c->way_shift;
	c->bytes		= bytes;
	c->indices		= indices;
	c->access		= 0;

	int a = assoc;
	while(a & (a-1)) a++;
	c->way_mask		= (a-1) << c->way_shift;

	c->lines		= calloc(indices, sizeof(cache_line *));
	if(!(c->lines))
		return E_SYS_NOMEM;

	int i, j;
	for(i=0; i<indices; i++) {
		c->lines[i] = malloc(assoc*sizeof(cache_line *));
		if(!(c->lines[i]))
			return E_SYS_NOMEM;
		for(j=0; j<assoc; j++) {
			c->lines[i][j] = malloc(sizeof(cache_line)+bytes);
			if(!(c->lines[i][j]))
				return E_SYS_NOMEM;

			// internally invariant values must be set properly
			c->lines[i][j]->lru = 0;
			c->lines[i][j]->writing = 0;
		}
	}
	
	return E_OKAY;
}

cache_error
destroy_cache(CACHE *c) {
	if(!c) return E_OKAY;
	if(c->lines) {
		int i,j;
		for(i=0; i<c->indices; i++) {
			for(j=0; j<c->ways; j++)
				free(c->lines[i][j]);
			free(c->lines[i]);
		}
	}
}

/****
 * get_line_index - Get the cache line at a given index
 *
 * c		- The cache to pull the line from
 * addr		- Address to extract index from
 * 
 * Returns a cache line matching the index of addr
 **/
static
inline
cache_line **
get_line_index(	CACHE *c,
				sim_addr addr) {
	size_t index = addr & c->index_mask;
	index >>= c->index_shift;
	
	return c->lines[index];
}

/****
 * get_line_addr = Get cache line at a given address
 *
 * c		- Cache to pull the line from
 * addr		- Address to search cache for
 * 
 * Returns a cache line matching the address or NULL if addr not in cache
 **/
static
inline
cache_line *
get_line_addr(	CACHE *c,
				sim_addr addr) {
	cache_line **line = get_line_index(c, addr);

	int i;
	for(i=0; i<c->ways; i++) {
		if((line[i]->tag & CACHE_VALID) && (line[i]->tag & c->tag_mask) == (addr & c->tag_mask))
			return line[i];
	}

	return NULL;
}

/****
 * validate_parameters - Check cache access input
 *
 * c		- Cache being accessed
 * addr		- Address being accessed
 * len		- Length of access
 *
 * Returns E_OKAY if parameters are legal, else returns appropriate error
 **/
static
inline
cache_error
validate_parameters(	CACHE *c,
						cache_addr addr,
						uint8_t len) {
//	if(len & (len-1))
//		return E_ALIGNMENT;
	
//	if((addr & c->byte_mask) & (len-1))
//		return E_ALIGNMENT;
	size_t off = addr & c->byte_mask;

	if((off+len) > c->bytes)
		return E_INVALID;

	return E_OKAY;
}

cache_error
cache_read_index(	CACHE *c,
					cache_addr index,
					cache_addr *tag,
					uint8_t len,
					uint8_t *buf) {
	size_t way;
	size_t byte;
	cache_line **line;
	cache_error err;

	if(err = validate_parameters(c, index, len))
		return err;
	
	way		= (index & c->way_mask) >> c->way_shift;
	byte	= index & c->byte_mask;

	if(way > c->ways)
		return E_INVALID;

	line = get_line_index(c, index);
	
	if(tag)
		*tag = line[way]->tag;
	
	if(buf && len)
		bcopy(line[way]->bytes+byte, buf, len);
	
	return E_OKAY;
}

cache_error
cache_write_index(	CACHE *c,
					cache_addr index,
					const cache_addr *tag,
					uint8_t len,
					const uint8_t *buf) {
	size_t way;
	size_t byte;
	cache_line **line;
	cache_error err;

	if(err = validate_parameters(c, index, len))
		return err;
	
	way		= (index & c->way_mask) >> c->way_shift;
	byte	= index & c->byte_mask;
	
	if(way > c->ways)
		return E_INVALID;

	line = get_line_index(c, index);
	
	// we cannot allow the tag to change on a line we're writing back
	if(line[way]->writing)
		return E_CACHE_BUSY;

	if(tag)
		line[way]->tag = *tag;
	
	// if the line is valid record it as an access
	if(line[way]->tag & CACHE_VALID)
		line[way]->lru = c->access++;		

	if(buf && len)
		bcopy(buf, line[way]->bytes+byte, len);
}

cache_error
cache_read_addr(	CACHE *c,
					cache_addr addr,
					cache_addr *tag,
					uint8_t len,
					uint8_t *buf) {
	size_t byte;
	cache_line *line;
	cache_error err;

	if(err = validate_parameters(c, addr, len))
		return err;
	
	byte	= addr & c->byte_mask;
	line	 = get_line_addr(c, addr);
	
	if(!line)
		return E_CACHE_MISS;

	if(tag)
		*tag = line->tag;
	
	// our LRU is smart, it includes writes AND reads
	if(line->tag & CACHE_VALID)
		line->lru = c->access++;

	if(buf && len)
		bcopy(line->bytes+byte, buf, len);
	
	return E_CACHE_HIT;
}

cache_error
cache_write_addr(	CACHE *c,
					cache_addr addr,
					const cache_addr *tag,
					uint8_t len,
					const uint8_t *buf) {
	size_t byte;
	cache_line *line;
	cache_error err;

	if(err = validate_parameters(c, addr, len))
		return err;
	
	byte	= addr & c->byte_mask;
	line 	= get_line_addr(c, addr);
	
	if(!line)
		return E_CACHE_MISS;
	
	// we need to protect cache data during a writeback
	if(line->writing)
		return E_CACHE_BUSY;

	if(tag)
		line->tag = *tag;
	else
		// We need to do a write back before replacing this line!
		line->tag |= CACHE_DIRTY;

	if(line->tag & CACHE_VALID)
		line->lru = c->access++;

	if(buf && len)
		bcopy(buf, line->bytes+byte, len);
	
	return E_CACHE_HIT;
}

cache_error
cache_insert_addr(	CACHE *c,
					cache_addr addr,
					const uint8_t *buf,
					cache_addr *wb) {
	size_t byte;
	cache_addr index;
	cache_line *aline;
	cache_line **line;
	cache_line *nline;
	cache_error err;

	if(err = validate_parameters(c, addr, c->bytes))
		return err;
	
	byte	= addr & c->byte_mask;
	
	// You must fill the cache line on insert!
	if(byte != 0)
		return E_INVALID;

	aline	= get_line_addr(c, addr);
	
	// If the address is already in the cache we're done!
	if(aline) {
		aline->tag = CACHE_VALID;
		aline->tag |= (c->tag_mask & addr);
		bcopy(buf, aline->bytes, c->bytes);
		return E_CACHE_HIT;
	}
	
	index	= addr & ~(c->tag_mask);
	line	= get_line_index(c, index);
	
	nline = NULL;

	int i;
	int busy = 0;
	for(i=0; i<c->ways; i++) {
		// we cannot access a line that is in the process of being written
		if(line[i]->writing) {
			busy = 1;
			continue;
		}
		
		// invalid lines are great for writing over :)
		if(!(line[i]->tag & CACHE_VALID)) {
			nline = line[i];
			break;
		}

		// Order of precidence for cache replacing:
		// 1. !valid
		// 2. !dirty
		// 3. smallest LRU
		if(!(line[i]->tag & CACHE_LOCKED) && (!nline || 
			(!(line[i]->tag & CACHE_DIRTY) && (nline->tag & CACHE_DIRTY))
			|| ((line[i]->tag & CACHE_DIRTY) == (nline->tag & CACHE_DIRTY) &&
			nline->lru > line[i]->lru)))
			nline = line[i];
	}
	
	// it is possible that all of the cache lines are locked or busy...
	if(!nline)
		return (busy ? E_CACHE_BUSY : E_CACHE_FULL);
	
	// We couldn't find a clean cache line, so we tell the client to preform a
	// write back and then call us again, as a hit we tell them who to write back
	if((nline->tag & CACHE_VALID) && (nline->tag & CACHE_DIRTY)) {
		// create a legal cache address
		if(wb)
			*wb = (nline->tag & c->tag_mask) | (addr & c->index_mask);
		return E_CACHE_WRITEBACK;
	}

	nline->tag = CACHE_VALID;
	nline->tag |= (c->tag_mask & addr);
	nline->lru = c->access++;
	bcopy(buf, nline->bytes, c->bytes);

	return E_OKAY;
}

cache_error
cache_open_writeback(	CACHE *c,
						cache_addr addr,
						uint8_t *buf) {
	cache_error err;
	cache_line *line;

	if(err = validate_parameters(c, addr, c->bytes))
		return err;

	line = get_line_addr(c, addr);

	if(!line)
		return E_CACHE_MISS;
	
	if(!(line->tag & CACHE_DIRTY))
		return E_CACHE_CLEAN;
	
	// set busy flag until client completes writeback
	line->writing = 1;
	if(buf)
		bcopy(line->bytes, buf, c->bytes);
	
	return E_OKAY;
}

cache_error
cache_close_writeback(	CACHE *c,
						cache_addr addr) {
	cache_error err;
	cache_line *line;

	if(err = validate_parameters(c, addr, c->bytes))
		return err;

	line = get_line_addr(c, addr);

	if(!line)
		return E_CACHE_MISS;
	
	// remove busy flag, clear dirty flag
	line->writing = 0;
	line->tag &= ~CACHE_DIRTY;

	return E_OKAY;
}

cache_error
cache_abort_writeback(	CACHE *c,
						cache_addr addr) {
	cache_error err;
	cache_line *line;

	if(err = validate_parameters(c, addr, c->bytes))
		return err;

	line = get_line_addr(c, addr);

	if(!line)
		return E_CACHE_MISS;
	
	// remove busy flag, line remains dirty though
	line->writing = 0;

	return E_OKAY;

}

